#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef struct {int v,w,nxt;}edge;

int h[110],wood[110],n,kk,top,stk[110],cnt;
ll dis[110],f[110][110][55],g[110][110][55];

edge e[110];

void link(int x,int y,int w){e[++cnt] = (edge){y,w,h[x]};h[x] = cnt;}

template <typename tp>
void upd(tp &x,tp y) {x = x < y ? x : y;}

void dfs(int x){
	stk[++top] = x;
	for(int i = h[x];i;i = e[i].nxt){
		int y = e[i].v;
		dis[y] = dis[x] + e[i].w;
		dfs(y);
		for(int tt = 1;tt <= top;tt++){
			int p = stk[tt];
			for(int j = kk;j >= 0;j--){
				f[x][p][j] += f[y][p][0];
				g[x][p][j] += f[y][x][0];
				for(int d = 1;d <= j;d++){
					upd(f[x][p][j],f[x][p][j-d] + f[y][p][d]);
					upd(g[x][p][j],g[x][p][j-d] + f[y][x][d]);
				}
			}
		}
	}
	for(int i = 1;i <= top;i++){
		int p = stk[i];
		for(int j = 0;j <= kk;j++){
			if(j > 0) f[x][p][j] = min(f[x][p][j]+(dis[x] - dis[p]) * wood[x],g[x][p][j-1]);
			else f[x][p][j] += (dis[x] - dis[p]) * wood[x];
		}
	}
	top--;
}

int main (){
	scanf("%d %d",&n,&kk);
	int fa,w;
	for(int i = 1;i <= n;i++){
		scanf("%d %d %d",&wood[i],&fa,&w);
		link(fa,i,w);
	}
	dfs(0);
	printf("%lld\n",f[0][0][kk]);
	return 0;
}
